package my.jwds.p646;

import com.alibaba.fastjson.JSON;

import java.util.Arrays;

public class findLongestChain {

    public static void main(String[] args) {
        findLongestChain obj = new findLongestChain();
        int[][] pairs = JSON.parseObject("[[9,10],[9,10],[4,5],[-9,-3],[-9,1],[0,3],[6,10],[-5,-4],[-7,-6]]",int[][].class);
        obj.sort(pairs,0,pairs.length-1);
        for (int[] pair : pairs) {
            System.out.println(Arrays.toString(pair));;
        }
        long start = System.currentTimeMillis();
        System.out.println(obj.findLongestChain(pairs));
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }

    public int findLongestChain(int[][] pairs) {
        sort(pairs,0,pairs.length-1);
        int last=pairs[0][1],res = 1;
        for (int i = 1; i < pairs.length; i++) {
            if (last < pairs[i][0]){
                res++;
                last = pairs[i][1];
            }
        }

        return res;
    }


    private void sort(int[][]pairs,int lower,int upper){
        if (lower >= upper)return;
        int num[] = pairs[lower],start = lower,end = upper;
        boolean right = true;
        while(start < end){
            if (right){
                if (num[1] > pairs[end][1]){
                    pairs[start] = pairs[end];
                    right = false;
                    start ++;
                }else{
                    end --;
                }

            }else{
                if (num[1] < pairs[start][1]){
                    pairs[end] = pairs[start];
                    right = true;
                    end --;
                }else{
                    start ++;
                }
            }
        }

        pairs[start] = num;
        sort(pairs,lower,start-1);
        sort(pairs,start+1,upper);
    }
}